import { random, swap } from 'helper/sortTest'

/**
 * NOTE: 排序算法
 */

// 归并排序算法
export function mergeSort(arr: number[]) {
  _mSort(arr, 0, arr.length - 1)
}

function _mSort(arr: number[], left: number, right: number) {
  if (left >= right) {
    return
  }
  // tslint:disable-next-line:no-bitwise
  let mid = left + ((right - left) >> 1)
  _mSort(arr, left, mid)
  _mSort(arr, mid + 1, right)
  if (arr[mid] > arr[mid + 1]) {
    merge(arr, left, mid, right)
  }
}

function merge(arr: number[], l: number, mid: number, r: number) {
  let tmp: number[] = []
  for (let i = l; i <= r; i++) {
    // 从 0 开始
    tmp[i - l] = arr[i]
  }

  let i = l
  let j = mid + 1

  for (let k = l; k < r + 1; k++) {
    if (i > mid) {
      arr[k] = tmp[j - l]
      j++
    } else if (j > r) {
      arr[k] = tmp[i - l]
      i++
    } else if (tmp[i - l] < tmp[j - l]) {
      arr[k] = tmp[i - l] // 将 arr[k] 位置的值替换
      i++
    } else {
      arr[k] = tmp[j - l] // arr[k] 位置的值为 j 位置的值
      j++
    }
  }
  // 1. 拷贝 [left...right] 的值到 temp 中
  // 两个数组, 两个指针 i, j
  // 循环将 arr[left ... right] 位置的按大小进行交换

}

export function quickSort(arr: number[]) {
  _quickSort(arr, 0, arr.length - 1)
}

function _quickSort(arr: number[], l: number, r: number) {
  if (l >= r) {
    return
  }

  // 分区
  const p = partition(arr, l, r)
  // 根据 p 下标进行分区
  _quickSort(arr, l, p - 1)
  _quickSort(arr, p + 1, r)
}

function partition(arr: number[], l: number, r: number): number {
  // 随机在 l, r 之间选择一个基点的下标
  let index = random(l, r) // 随机选择基点
  // 将 index 和 l 交换
  swap(arr, l, index)
  let v = arr[l] // 基点
  let j = l
  for (let i = l + 1; i <= r; i++) {
    if (arr[i] < v) {
      j++
      if (j === i) {
        continue
      }
      swap(arr, j, i)
    }
  }
  swap(arr, l, j)
  return j
}

export function quickSortThreeWay(arr: number[]) {
  _quickSortThreeWay(arr, 0, arr.length - 1)
}

// arr[l+1 ... lt ) < v ; arr[lt ... gt-1] == v ; arr[gt...r] > v
function _quickSortThreeWay(arr: number[], l: number, r: number) {
  if (l >= r) {
    return
  }
  let index = random(l, r)

  swap(arr, index, l)

  let v = arr[l]

  let lt = l

  let gt = r + 1

  let i = l + 1

  while (i < gt) {
    if (arr[i] < v) { // 将
      lt++
      if (i === lt) {
        i++
        continue
      }
      swap(arr, i, lt)
      i++
    } else if (arr[i] > v) { // 将后面的数移动到前面来, 再次查看当前位置 i, 同时将 gt 左移动一个
      gt--
      swap(arr, i, gt)
    } else {
      i++
    }
  }

  swap(arr, lt, l)

  _quickSortThreeWay(arr, l, lt - 1)
  _quickSortThreeWay(arr, gt, r)
}
